package cn.arnold.sort;

import java.util.Arrays;

public class ShellSort {

    public static void main(String[] args) {
        int[] array = {8, 9, 1, 7, 2, 3, 5, 4, 6, 0};
        sort(array);
        System.out.println(Arrays.toString(array));
    }

    public static void sort(int[] array) {
        // 推导
        // {8, 9, 1, 7, 2, 3, 5, 4, 6, 0}
        // 第一次整合
      /*  for (int i = 5; i < array.length; i++) {
            int j = i;
            int temp = array[j];                // 待插入的元素array[5]
            if (array[j] < array[j - 5]) {      // array[5]<array[0]
                // 移动找位置
                while (j - 5 >= 0 && temp < array[j - 5]) {
                    array[j] = array[j - 5];
                    j -= 5;
                }
                // 退出while循环后找到了位置，将要插入的元素插入到此位置
                array[j] = temp;
            }
        }
        System.out.println("第一次排序后：" + Arrays.toString(array));
*/
        // 增量gap，并逐步缩小增量
        for (int gap = array.length / 2; gap > 0; gap /= 2) {
            // 依次对每个分组进行直接插入排序
            for (int i = gap; i < array.length; i++) {
                int j = i;
                int temp = array[j];                // 待插入的元素array[5]
                if (array[j] < array[j - gap]) {      // array[5]<array[0]
                    // 移动找位置
                    while (j - gap >= 0 && temp < array[j - gap]) {
                        array[j] = array[j - gap];
                        j -= gap;
                    }
                    // 退出while循环后找到了位置，将要插入的元素插入到此位置
                    array[j] = temp;
                }
            }
            System.out.println("第趟后：" + Arrays.toString(array));
        }
    }
}
